Chapter 1: Array/String

1. Two Sum (LC1)

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given numbers = [2, 7, 11, 15], target = 9,

Because numbers[0] + numbers[1] = 2 + 7 = 9, return [0, 1].

Solution:

O(n) runtime, O(n) space



In [1]:

    
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = (numbers, target) => {
    for (const i of [...Array(numbers.length).keys()]) {
        if (numbers.includes(target - numbers[i])) {
            const j = +Object.keys(numbers).find(key => numbers[key] == target - numbers[i] && key != i)
            if (j) {
                return [i, j]
            }
        }
    }
    return []
}

2. Two Sum II - Input array is sroted (LC167)

Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.

Solution

O(n) runtime, O(1) space

Two pointers



In [22]:

    
var twoSum =(numbers, target) => {
    let [i, j] = [0, numbers.length - 1]
    while (i < j) {
        const sum = numbers[i] + numbers[j]
        if (sum < target) i++
        else if (sum > target) j--
        else return [i+1, j+1]
    }
}



In [25]:

    
twoSum([1, 1, 2, 4, 8], 2)









    Out[25]:





[ 1, 2 ]

3. Two Sum III - Data structure design

Question

Design and implement a TwoSum class. It should support the following operations: add and find.

add(input) – Add the number input to an internal data structure.

find(value) – Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5); find(4) -> true; find(7) -> false



In [14]:

    
var createTwoSum = () => {
    let numbers = [];
    return {
        add: number => {numbers.push(number)},
        find: target => {
            let [i, j] = [0, numbers.length - 1]
            while (i < j) {
                const sum = numbers[i] + numbers[j]
                if (sum < target) i++
                else if (sum > target) j--
                else return true
            }
            return false
        }
    }
}



In [15]:

    
myTS = createTwoSum()









    Out[15]:





{ add: [Function: add], find: [Function: find] }



In [16]:

    
myTS.add(3)



In [17]:

    
myTS.add(8)



In [18]:

    
myTS.find(11)









    Out[18]:





true



In [19]:

    
myTS.find(1)









    Out[19]:





false



In [ ]: